package interview.huawei.tjt.training.huisu;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
 *
 * 示例：
 *
 * 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 */
// 回溯法解法
public class MinSubArrayLen {

    private static int len = 999;
    private static LinkedList<Integer> path = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String string = sc.nextLine();
            int s = Integer.parseInt(string);
            String[] str = sc.nextLine().split(",");
            int[] nums = new int[str.length];
            int sum = 0;
            for (int i = 0; i < str.length; i++) {
                if (!str[i].equals("") && str[i] != null) {
                    nums[i] = Integer.parseInt(String.valueOf(str[i]));
                    sum += nums[i];
                }
            }
            if (sum < s) {
                System.out.println("0");
            } else {
                helper(nums, s, 0, 0);
                System.out.println(len);
            }
        }
    }

    private static void helper (int[] nums, int s, int sum, int startIndex) {
        // 结束条件
        if (sum >= s) {
            if (path.size() < len) {
                len = path.size();
            }
        }

        for (int i = startIndex;i < nums.length; i ++) {
            path.add(nums[i]);
            helper(nums, s, sum + nums[i], i + 1);
            //回溯
            path.removeLast();
        }
    }

}
